package com.lfg.leetcode.leetcode300;


import java.util.Arrays;

public class No377combinationSum4 {
    public static void main(String[] args) {
        int ret = combinationSum4(new int[]{
                1,2,3
        }, 4);
        System.out.println(ret);

    }

    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        Arrays.sort(nums);
        dp[0] = 1;
        for(int t =1;t<=target;t++) {
            for (int num : nums) {
                int index = t - num;
                if (index < 0) {
                    break;
                }
                dp[t] += dp[index];
            }
        }

        return dp[dp.length-1];
    }
}



